- Title
- Faster fixed-parameter tractable algorithms for matching and packing problems
- Creator
- Fellows, M. R.; Knauer, C.; Nishimura, N.; Ragde, P.; Rosamond, F.; Stege, U.; Thilikos, D. M.; Whitesides, S.
- Relation
- Algorithmica Vol. 52, Issue 2, p. 167-176
- Publisher Link
- http://dx.doi.org/10.1007/s00453-007-9146-y
- Publisher
- Springer
- Resource Type
- journal article
- Date
- 2008
- Description
- We obtain faster algorithms for problems such as r-dimensional matching and r-set packing when the size k of the solution is considered a parameter. We first establish a general framework for finding and exploiting small problem kernels (of size polynomial in k). This technique lets us combine Alon, Yuster and Zwick’s color-coding technique with dynamic programming to obtain faster fixed-parameter algorithms for these problems. Our algorithms run in time O(n+2 O(k)), an improvement over previous algorithms for some of these problems running in time O(n+k O(k)). The flexibility of our approach allows tuning of algorithms to obtain smaller constants in the exponent.
- Subject
- parameterized complexity; fixed parameter tractable; graph matching; set packing; color coding
- Identifier
- http://hdl.handle.net/1959.13/41262
- Identifier
- uon:4698
- Identifier
- ISSN:1432-0541
- Language
- eng
- Reviewed
- Hits: 4075
- Visitors: 4024
- Downloads: 0
Thumbnail | File | Description | Size | Format |
---|